package code.notdo;

import javax.sound.sampled.Line;
import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

/**
 * author : yeswater
 * date : 2023/12/16
 * <p>
 * 课程表
 * <p>
 * 是否可以完成所有课程的学习 可以返回 true 不可以 返回 false
 */

public class T207 {
    
    /* 宫水三叶题解 */
    
    int N = 100010, M = 5010; // 这里是为什么??
    int[] in = new int[N], he = new int[N], e = new int[M], ne = new int[M];
    int idx;
    
    void add(int a, int b) {
        e[idx] = b;
        ne[idx] = he[a];
        he[a] = idx++;
        in[b]++;
    }
    
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        Arrays.fill(he, -1);
        for (int[] info : prerequisites) {
            add(info[1], info[0]);
        }
        int ans = 0;
        Deque<Integer> d = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (in[i] == 0) d.addLast(i);
        }
        while (!d.isEmpty()) {
            int t = d.pollFirst();
            ans++;
            for (int i = he[t]; i != -1; i = ne[i]) {
                int j = e[i];
                if (--in[j] == 0) {
                    d.addLast(j);
                }
            }
        }
        return ans == numCourses;
    }
}
